﻿#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;




//int main()
//{
//    long long int n;
//    cin >> n;
//    string s;
//    while (n)
//    {
//        n--;
//        s += n % 26 + 'A';
//        n /= 26;
//    }
//    reverse(s.begin(), s.end());
//    cout << s;
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    vector<int> a(n);
//    vector<int> dp(n + 1);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//        dp[i + 1] = dp[i] + a[i];
//    }
//    int count = 0;
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            if ((dp[i] - dp[j]) % k == 0)
//            {
//                count++;
//            }
//        }
//    }
//    cout << count << endl;
//    return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    vector<vector<int>> a(n, vector<int>(2));
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i][0] >> a[i][1];
//    }
//    int count = 0;
//    int ret = 1;
//    int l = 1;
//    while (1)
//    {
//        for (int i = 0; i < n; i++)
//        {
//            count += (a[i][0] / l) * (a[i][1] / l);
//        }
//        if (count >= k)
//        {
//            ret = l;
//            count = 0;
//        }
//        else
//        {
//            break;
//        }
//        l++;
//    }
//    cout << ret;
//    return 0;
//}




//#include <iostream>
//using namespace std;
//int L[100005];
//int W[100005];
//int main()
//{
//    int N, K;
//    cin >> N >> K;
//    for (int i = 1; i <= N; i++)
//        cin >> L[i] >> W[i];
//    int i = 10000;
//    while (true)
//    {
//        int sum = 0, num1, num2;
//        for (int j = 1; j <= N; j++)
//        {
//            num1 = L[j] / i;
//            num2 = W[j] / i;
//            sum += num1 * num2;
//        }
//        if (sum >= K)
//            break;
//        i--;
//    }
//    cout << i;
//    return 0;
//}


// https://www.nowcoder.com/practice/56ea71d1f4e94de2aaec10e985874cce?tpId=196&tqId=40269&ru=/exam/oj
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param nums1 int整型vector
//     * @param nums2 int整型vector
//     * @return int整型vector
//     */
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size(), m = nums2.size();
//        sort(nums1.begin(), nums1.end());
//        sort(nums2.begin(), nums2.end());
//        int left = 0, right = 0;
//
//        vector<int> ret;
//        while (left < n && right < m)
//        {
//            if (nums1[left] > nums2[right])
//            {
//                right++;
//            }
//            else if (nums1[left] < nums2[right])
//            {
//                left++;
//            }
//            else if (nums1[left] == nums2[right])
//            {
//                ret.push_back(nums1[left]);
//                left++;
//                right++;
//            }
//            while (left < n && nums1[left] == nums1[left - 1])
//            {
//                left++;
//            }
//            while (right < m && nums2[right] == nums2[right - 1])
//            {
//                right++;
//            }
//
//        }
//        return ret;
//    }
//};



// https://www.nowcoder.com/practice/8d3643ec29654cf8908b5cf3a0479fd5?tpId=308&tqId=40462&ru=/exam/oj
//int main() {
//    stack<char> st;
//    string str;
//    cin >> str;
//    for (int i = 0; i < str.size(); i++) {
//        if (st.empty()) {
//            st.push(str[i]);
//        }
//        else {
//            if (st.top() == str[i])
//                st.pop();
//            else st.push(str[i]);
//        }
//    }
//    if (st.empty()) cout << 0 << endl;
//    else {
//        int n = st.size();
//        char a[n];
//        for (int i = n - 1; i >= 0; i--) {
//            a[i] = st.top();
//            st.pop();
//        }
//        for (int i = 0; i < n; i++) cout << a[i];
//    }
//
//    return 0;
//}

// 64 位输出请用 printf("%lld")


// https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpId=230&tqId=39751&ru=/exam/oj
//int main()
//{
//    int n;
//    cin >> n;
//
//    vector<int> a(n);
//    vector<int> dp(n + 1);
//
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//
//    }
//    if (n == 1)
//    {
//        return a[0];
//    }
//
//    for (int i = 2; i <= n; i++)
//    {
//        dp[i] = min(dp[i - 2] + a[i - 2], dp[i - 1] + a[i - 1]);
//    }
//    cout << dp[n];
//}



// https://www.nowcoder.com/questionTerminal/2c6a0a8e1d20492f92941400036e0890
//int main()
//{
//    int n;
//    cin >> n;
//    vector<string> s(n);
//    string a;
//    string b;
//    cin >> a >> b;
//    int ret = INT_MAX;
//    int x = -1, y = -1;
//    if (n <= 1 || a.size() == 0 || b.size() == 0)
//    {
//        ret = -1;
//
//    }
//    else
//    {
//        for (int i = 0; i < n; i++)
//        {
//            cin >> s[i];
//            if (s[i] == a)
//            {
//                x = i;
//            }
//            else if (s[i] == b)
//            {
//                y = i;
//            }
//            if (x != -1 && y != -1)
//            {
//                ret = min(ret, abs(x - y));
//            }
//        }
//
//    }
//    if (x == -1 || y == -1)
//    {
//        ret = -1;
//    }
//    cout << ret;
//    return 0;
//}


//int main()
//{
//    int n, x;
//    cin >> n >> x;
//    vector<int> a(n + 1,0);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//    }
//    int left = 1, right = 1;
//    long long int sum = a[0];
//    int ret = n;
//    int l = 1, r = 1;
//    while (right <= n)
//    {
//        if (sum < x)
//        {
//            sum += a[right++];
//        }
//        while (sum >= x)
//        {
//            if (ret > right - left)
//            {
//                ret = right - left;
//                l = left, r = right;
//            }
//            sum -= a[left++];
//        }
//
//    }
//    cout << l << " " << l + ret-1;
//    return 0;
//}


//int main()
//{
//    long long int n, k;
//    cin >> n >> k;
//    long long int a = 0;
//    priority_queue<long long int> q;
//    long long int sum = 0;
//    int flag = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a;
//        q.push(a);
//        sum += a;
//    }
//    while (k-- && q.size())
//    {
//        long long int t = q.top();
//        q.pop();
//        if (t % 2)
//        {
//            while (t % 2 && q.size())
//            {
//                t = q.top();
//                q.pop();
//            }
//        }
//        if (t % 2 == 0)
//        {
//            sum -= t;
//            t /= 2;
//            sum += t;
//            q.push(t);
//        }
//    }
//    cout << sum;
//
//    return 0;
//}


// https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj
//class Solution {
//public:
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool vis[101][101];
//    int m, n;
//    bool dfs(vector<string>& board, int i, int j, int pos, string& word)
//    {
//        if (pos == word.size() - 1)
//        {
//            return true;
//        }
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int a = i + dx[k], b = j + dy[k];
//            if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && board[a][b] == word[pos + 1])
//            {
//                if (dfs(board, a, b, pos + 1, word))
//                {
//                    return true;
//                }
//            }
//        }
//        vis[i][j] = false;
//        return false;
//    }
//    bool exist(vector<string>& board, string word)
//    {
//        m = board.size(), n = board[0].size();
//        if (n <= 0 || word.size() > m * n)
//        {
//            return false;
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    if (dfs(board, i, j, 0, word))
//                    {
//                        return true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//};
//
//int n;
//int main()
//{
//    cin >> n;
//    int a = 0, b = 1, c = 1;
//    while (n > c)
//    {
//        a = b;
//        b = c;
//        c = a + b;
//    }
//    cout << min(c - n, n - b) << endl;
//    return 0;
//}


//int main()
//{
//	int q;
//	cin >> q;
//	long long int a, b, c;
//	long long int m = 0;
//	long long int ret = 0;
//	for (int i = 0; i < q; i++)
//	{
//		cin >> a >> b >> c;
//		m = min(a, min(b, c));
//		if (m == a)
//		{
//			ret += m * 2;
//			if ((b - m) > 2)
//			{
//				ret += (b - m) - 1;
//			}
//			else
//			{
//				ret += (b - m) / 2;
//			}
//		}
//		else if (m == b)
//		{
//			ret += b * 2;
//		}
//		else if (m == c)
//		{
//			ret += c * 2;
//			if ((b - m) > 2)
//			{
//				ret += (b - m) - 1;
//			}
//			else
//			{
//				ret += (b - m) / 2;
//			}
//		}
//		cout << ret << endl;
//		ret = 0;
//	}
//	return 0;
//}


//class Solution {
//public:
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int m, n;
//    bool vis[1001][1001] = { 0 };
//    int rotApple(vector<vector<int> >& grid) {
//        m = grid.size(), n = grid[0].size();
//        queue<pair<int, int>> q;
//        int ret = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 2)
//                {
//                    q.push({ i,j });
//                }
//            }
//        }
//        while (q.size())
//        {
//            ret++;
//            int s = q.size();
//            while (s--)
//            {
//                auto [a, b] = q.front();
//                q.pop();
//                for (int i = 0; i < 4; i++)
//                {
//                    int x = a + dx[i], y = b + dy[i];
//                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
//                    {
//                        q.push({ x,y });
//                        vis[x][y] = true;
//                    }
//                }
//            }
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 1 && !vis[i][j])
//                {
//                    return -1;
//                }
//            }
//        }
//        return ret - 1;
//    }
//};
//
//
//
//// https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&ru=/exam/oj
//class Solution {
//public:
//    int j = 1;
//    int LastRemaining_Solution(int n, int m)
//    {
//        vector<int> a(n + 1, 1);
//        int i = 0, j = 0;
//        int k = 0;
//        while (i != n - 1)
//        {
//            if (a[k])
//            {
//                j++;
//            }
//            if (j == m)
//            {
//                a[k] = 0;//退出
//                i++;
//                j = 0;
//            }
//            k++;
//            if (k == n)
//            {
//                k = 0;
//                while (a[k] == 0)
//                {
//                    k++;
//                }
//            }
//        }
//        for (int i = 0; i < n; i++)
//        {
//            if (a[i])
//            {
//                return i;
//            }
//        }
//        return -1;
//    }
//};
//
//// https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475?tpId=196&tqId=37176&ru=/exam/oj
//class Solution {
//public:
//    string solve(string s, string t) {
//        if (s.empty())
//        {
//            return t;
//        }
//        if (t.empty())
//        {
//            return s;
//        }
//        string ret;
//        int i = s.size() - 1;
//        int j = t.size() - 1;
//        int tmp = 0;
//        while (i >= 0 || j >= 0)
//        {
//            if (i >= 0)
//            {
//                tmp += s[i--] - '0';
//            }
//            if (j >= 0)
//            {
//                tmp += t[j--] - '0';
//            }
//            ret += tmp % 10 + '0';
//            tmp /= 10;
//        }
//        if (tmp)
//        {
//            ret += tmp + '0';
//        }
//        reverse(ret.begin(), ret.end());
//        return ret;
//
//    }
//};


///**
// * struct ListNode {
// *	int val;
// *	struct ListNode *next;
// *	ListNode(int x) : val(x), next(nullptr) {}
// * };
// */
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param head1 ListNode类
//     * @param head2 ListNode类
//     * @return ListNode类
//     */
//    ListNode* Reverse(ListNode* head)
//    {
//        if (head == nullptr)
//        {
//            return nullptr;
//        }
//        ListNode* cur = head;
//        ListNode* prev = nullptr;
//
//        while (cur)
//        {
//            ListNode* rear = cur->next;
//            cur->next = prev;
//            prev = cur;
//            cur = rear;
//        }
//        return prev;
//    }
//    ListNode* addInList(ListNode* head1, ListNode* head2)
//    {
//        if (head1->next == nullptr)
//        {
//            return head2;
//        }
//        if (head2->next == nullptr)
//        {
//            return head1;
//        }
//        head1 = Reverse(head1);
//        head2 = Reverse(head2);
//        ListNode* cur1 = head1;
//        ListNode* cur2 = head2;
//        ListNode* ret = new ListNode(0);
//        ListNode* cur3 = ret;
//        int flag = 0;
//        while (cur1 || cur2 || flag)
//        {
//            int tmp = flag;
//            if (cur1)
//            {
//                tmp += cur1->val;
//            }
//            if (cur2)
//            {
//                tmp += cur2->val;
//            }
//            flag = tmp / 10;
//            tmp %= 10;
//            cur3->next = new ListNode(tmp);
//            cur3 = cur3->next;
//            if (cur1)
//            {
//                cur1 = cur1->next;
//            }
//            if (cur2)
//            {
//                cur2 = cur2->next;
//
//            }
//        }
//        return Reverse(ret->next);
//
//    }
//};


//int main()
//{
//	string s;
//	string t;
//    cin >> s;
//    cin >> t;
//    int m = s.size();
//    int n = t.size();
//
//    long long int tmp1 = 0, tmp2 = 0;
//    long long int a = 10;
//    for (int i = 0; i < m; i++)
//    {
//
//        tmp1 = tmp1 * a + (s[i] - '0');
//        //a *= 10;
//    }
//    a = 10;
//    for (int i = 0; i < n; i++)
//    {
//        tmp2 = tmp2 * a + (t[i] - '0');
//        //a *= 10;
//    }
//    cout << tmp1 * tmp2;
//	return 0;
//}


//#include <string>
//class Solution {
//public:
//    string solve(string s, string t)
//    {
//        reverse(s.begin(), s.end());
//        reverse(t.begin(), t.end());
//        int m = s.size();
//        int n = t.size();
//        vector<int> sum(n + m);
//        int flag = 0; // 进位
//
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                int tmp1 = s[i] - '0';
//                int tmp2 = t[j] - '0';
//                sum[i + j] += tmp1 * tmp2;
//            }
//        }
//        string ret;
//        int tmp = 0;
//
//        for (int i = 0; i < (m + n); i++)
//        {
//            tmp = sum[i] + flag;
//            ret += tmp % 10 + '0';
//            flag = tmp / 10;
//        }
//        while (flag)
//        {
//            ret += flag % 10 + '0';
//            flag /= 10;
//        }
//        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};


//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//    int left = 0;
//    int right = 0;
//    int l = 0;
//    int m = 0;
//    while (right < s.size())
//    {
//        if (s[right] >= '0' && s[right] <= '9')
//        {
//            left = right;
//            while (s[right] >= '0' && s[right] <= '9')
//            {
//                right++;
//            }
//            if ((right - left) > m)
//            {
//                m = right - left;
//                l = left;
//            }
//            right--;
//        }
//        right++;
//    }
//    cout << s.substr(l, m);
//    return 0;
//}



//class Solution {
//public:
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int vis[201][201] = { 0 };
//    int m, n;
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        vis[i][j] = 1;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
//            {
//                dfs(grid, x, y);
//            }
//        }
//    }
//    int solve(vector<vector<char> >& grid)
//    {
//        m = grid.size(), n = grid[0].size();
//        int count = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1' && !vis[i][j])
//                {
//                    count++;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return count;
//    }
//};



//class Solution {
//public:
//    int MLS(vector<int>& arr)
//    {
//        sort(arr.begin(), arr.end());
//        int n = arr.size();
//        int count = 1;
//        int ret = 0;
//        for (int i = 1; i < n; i++)
//        {
//            if (arr[i] == arr[i - 1])
//            {
//                continue;
//            }
//            if (arr[i] - arr[i - 1] == 1)
//            {
//                count++;
//            }
//            else
//            {
//                count = 1;
//            }
//            ret = max(ret, count);
//        }
//        return ret;
//    }
//};




//int main()
//{
//    int n = 0, m = 0;;
//    cin >> n >> m;
//    vector<vector<char>> a(n + 1, vector<char>(m + 1));
//    vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if (a[i][j] == 'l')
//            {
//                dp[i][j] = 4;
//            }
//            if (a[i][j] == 'o')
//            {
//                dp[i][j] = 3;
//            }
//            if (a[i][j] == 'v')
//            {
//                dp[i][j] = 2;
//            }
//            if (a[i][j] == 'e')
//            {
//                dp[i][j] = 1;
//            }
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];
//        }
//    }
//    printf("%d", dp[n][m]);
//    return 0;
//
//}



//#include <iostream>
//#include <string>
//#include <bits/stdc++.h>
//using namespace std;
//
//int main()
//{
//    string s;
//    string ret;
//    cin >> s;
//    int right = s.size() - 1;
//    //int left = 0;
//    int count = 0;
//    while (right >= 0)
//    {
//        ret += s[right];
//        count++;
//        if (count % 3 == 0 && right)
//        {
//            ret += ',';
//        }
//        right--;
//    }
//    reverse(ret.begin(), ret.end());
//    cout << ret;
//    return 0;
//}



//#include<iostream>
//using namespace std;
//
//int jump(int n) {
//    if (n == 0)
//        return 0;
//    else if (n == 1)
//        return 1;
//    else if (n == 2)
//        return 2;
//    else
//        return jump(n - 1) + jump(n - 2);
//}
//
//int main() {
//    int num;
//    cin >> num;
//    cout << jump(num) << endl;
//    return 0;
//
//}



//#include <vector>
//class Solution {
//public:
//    bool IsContinuous(vector<int>& numbers)
//    {
//        sort(numbers.begin(), numbers.end());
//        int count0 = 0;
//        int len = 0;
//        for (int i = 0; i < numbers.size() - 1; i++)
//        {
//            if (numbers[i] == numbers[i + 1] && numbers[i])
//            {
//                return false;
//            }
//            if (numbers[i] == 0)
//            {
//                count0++;
//            }
//            else
//            {
//                len += numbers[i + 1] - numbers[i] - 1;
//            }
//        }
//        if (count0 >= len)
//        {
//            return true;
//        }
//        return false;
//    }
//};


//class Solution {
//public:
//    int fun(string& s, int begin, int end) {
//        //每个中心点开始扩展
//        while (begin >= 0 && end < s.length() && s[begin] == s[end]) {
//            begin--;
//            end++;
//        }
//        //返回长度
//        return end - begin - 1;
//    }
//    int getLongestPalindrome(string A) {
//        int maxlen = 1;
//        //以每个点为中心
//        for (int i = 0; i < A.length() - 1; i++)
//            //分奇数长度和偶数长度向两边扩展
//            maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1)));
//        return maxlen;
//    }
//};


//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    int n;
//    cin >> n;
//    vector<int> a(n);
//    int cost = 0, ret = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//    cost = a[0];
//    for (int i = 1; i < n; i++)
//    {
//        ret = max(ret, a[i] - cost);
//        cost = min(cost, a[i]);
//    }
//    cout << ret;
//    return 0;
//
//}
// 64 位输出请用 printf("%lld")


//#include <iostream>
//using namespace std;
//int n, m, x, y;
//long long dp[25][25];
//int main()
//{
//	cin >> n >> m >> x >> y;
//	x += 1; y += 1;
//	dp[0][1] = 1;
//	for (int i = 1; i <= n + 1; i++)
//	{
//		for (int j = 1; j <= m + 1; j++)
//		{
//			if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
//				j == y))
//			{
//				dp[i][j] = 0;
//			}
//			else
//			{
//				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//			}
//		}
//	}
//	cout << dp[n + 1][m + 1] << endl;
//	return 0;
//}


//#include <iostream>
//using namespace std;
//
//int main()
//{
//    long long int n, m, a, b;
//    cin >> n >> m >> a >> b;
//    long long int sum = 0;
//    //long long int x = n/2;
//    long long int y = 0;
//    //int k = 0;//记录差
////     long long int sum1 = 0;
////     long long int sum2 = 0;
//    for (long long int x = 0; ; x++)
//    {
//        if (n < 2 * x || m < x)
//        {
//            break;
//        }
//        long long apple = n - x * 2;
//        long long peach = m - x;
//        y = min(apple, peach / 2);
//        sum = max(sum, x * a + y * b);
//    }
//    cout << sum;
//    return 0;
//}


//#include <iostream>
//#include <algorithm>
//#include <string>
//using namespace std;
//
//int main()
//{
//    string s;
//    getline(cin, s);
//    int n = s.size();
//    reverse(s.begin(), s.end());
//
//    //int left = 0,right = 0;
//    for (int i = 0; i < n; )
//    {
//        int j = i;
//        while (j < n && s[j] != ' ')
//        {
//            j++;
//        }
//        reverse(s.begin() + i, s.begin() + j);
//        j++;
//        i = j;
//    }
//    cout << s;
//    return 0;
//}
//// 64 位输出请用 printf("%lld")



//int main()
//{
//	string s, t;
//	getline(cin, s);
//	getline(cin, t);
//	bool hash[300] = { 0 };
//	for (char ch : t) hash[ch] = true;
//	string ret;
//	for (auto ch : s)
//	{
//		if (!hash[ch])
//		{
//			ret += ch;
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}



class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        int left = -1, right = n;
        for (int i = 0; i < right; )
        {
            if (nums[i] == 0)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == 1)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
    }
};


class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1, right = nums.size();
        int i = 0;
        while (i < right)
        {
            if (nums[i] == 0)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == 1)
            {
                i++;
            }
            else {
                swap(nums[--right], nums[i]);
            }
        }
    }
};


class Solution
{
public:
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL)); // 种下⼀个随机数种⼦
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];

    }
    void qsort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }
        // 数组分三块
        int key = getRandom(nums, begin, end);
        int i = begin, left = begin - 1, right = end + 1;
        while (i < right)
        {
            if (nums[i] > key)
            {
                swap(nums[--right], nums[i]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                swap(nums[++left], nums[i++]);
            }
        }
        qsort(nums, begin, left);
        qsort(nums, right, end);
    }
};


class Solution
{
public:
    int qsort(vector<int>& nums, int l, int r, int k)
    {
        int i = l, left = l - 1, right = r + 1;
        int key = nums[(l + r) / 2];
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
        if (r - right + 1 >= k)
        {
            return qsort(nums, right, r, k);
        }
        else if (r - left >= k)


        {
            return key;
        }
        else
        {
            return qsort(nums, l, left, k + left - r);
        }
    }
    int findKthLargest(vector<int>& nums, int k)
    {

        return qsort(nums, 0, nums.size() - 1, k);
    }
};


class Solution
{
public:
    void qsort(vector<int>& stock, int l, int r, int k)
    {
        if (l >= r) return;
        int i = l, left = l - 1, right = r + 1;
        int key = stock[(left + right) / 2];
        while (i < right)
        {
            if (stock[i] < key)
            {
                swap(stock[++left], stock[i++]);
            }
            else if (stock[i] == key)
            {
                i++;
            }
            else
            {
                swap(stock[--right], stock[i]);
            }
        }
        if (left - l + 1 > k)
        {
            qsort(stock, l, left, k);
        }
        else if (right - l >= key)
        {
            return;
        }
        else
        {
            qsort(stock, right, r, k - right + l);
        }

    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        qsort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(),stock.begin() + cnt };

    }
};


class Solution {
public:
    void mergesort(vector<int>& nums, int left, int right)
    {
        if (left >= right)
            return;
        int mid = (left + right) / 2;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        vector<int> tmp(right - left + 1);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right)
        {
            tmp[i++] = nums[cur2++];
        }
        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }
    }
    vector<int> sortArray(vector<int>& nums)
    {
        mergesort(nums, 0, nums.size() - 1);
        return nums;

    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
//    {
//        ListNode* cur1 = l1;
//        ListNode* cur2 = l2;
//        ListNode* ret = new ListNode(0);
//        ListNode* cur = ret;
//        // if(l1->next == nullptr && l2->next == nullptr && !l1->val && !l2->val)
//        //     return ret;
//        // long long int a = 1;
//        // long long int tmp1 = 0;
//        // long long int tmp2 = 0;
//        int flag = 0;
//        while (cur1 || cur2 || flag)
//        {
//            if (cur1)
//            {
//                flag += cur1->val;
//                cur1 = cur1->next;
//            }
//            if (cur2)
//            {
//                flag += cur2->val;
//                cur2 = cur2->next;
//            }
//            cur->next = new ListNode(flag % 10);
//            flag /= 10;
//            cur = cur->next;
//        }
//        cur = ret->next;
//        return cur;
//    }
//};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head)
//    {
//        if (head == nullptr || head->next == nullptr) return head;
//        ListNode* ret = new ListNode(0);
//        ret->next = head;
//        ListNode* prev = ret;
//        ListNode* cur = prev->next;
//        ListNode* tail = cur->next;
//
//        ListNode* ttail = tail->next;
//        while (cur && tail)
//        {
//            prev->next = tail;
//            tail->next = cur;
//            cur->next = ttail;
//            prev = cur;
//            cur = prev->next;
//            if (cur)
//                tail = cur->next;
//            if (tail)
//                ttail = tail->next;
//        }
//        ret = ret->next;
//        return ret;
//    }
//};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution
//{
//public:
//    void reorderList(ListNode* head)
//    {
//        if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
//        {
//            return;
//        }
//        ListNode* slow = head;
//        ListNode* fast = head;
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        ListNode* tmp = new ListNode(0);
//        ListNode* cur = slow->next;
//        slow->next = nullptr;
//        while (cur)
//        {
//            ListNode* post = cur->next;
//            cur->next = tmp->next;
//            tmp->next = cur;
//            cur = post;
//        }
//        ListNode* cur1 = head;
//        ListNode* cur2 = tmp->next;
//        while (cur1)
//        {
//            ListNode* post1 = cur1->next;
//            cur1->next = cur2;
//            cur1 = cur2;
//            //处理逆序的那个链表过于短的情况
//            if (post1 == nullptr && cur2 && cur2->next)
//            {
//                break;
//            }
//            cur2 = post1;
//
//        }
//
//
//
//    }
//};


class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        stack<int> ret;
        int i = 0;

        for (auto& e : pushed)
        {
            ret.push(e);
            while (ret.size() && ret.top() == popped[i])
            {
                ret.pop();
                i++;
            }
        }
        if (i == popped.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};